package leetcode_top;

import org.junit.Test;
import java.util.*;

public class Ex130 {

    class Solution { //并查集：利用并查集将所有不需要改的位置都标记上
        int m,n;
        char[][] board;
        //改动原数组，将边界有关的O全部变成另外的字符最后再变回来
        public void solve(char[][] board) {
            if (board == null) return;
            this.m = board.length;
            this.n = board[0].length;
            this.board = board;
            UnionFindSet ufs = new UnionFindSet();
            int dummy = -1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O')  {
                        int cur = to1D(i, j);
                        if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                            ufs.union(cur, dummy);
                        } else {
                            if (i - 1 >= 0 && board[i - 1][j] == 'O')  {
                                ufs.union(cur, to1D(i - 1, j));
                            }
                            if (i + 1 < m && board[i + 1][j] == 'O')  {
                                ufs.union(cur, to1D(i + 1, j));
                            }
                            if (j - 1 >= 0 && board[i][j - 1] == 'O')  {
                                ufs.union(cur, to1D(i, j - 1));
                            }
                            if (j + 1 < n && board[i][j + 1] == 'O')  {
                                ufs.union(cur, to1D(i, j + 1));
                            }
                        }
                    }
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    //不与虚拟节点相连的O才进行转换
                    if (board[i][j] == 'O' && !ufs.isConnect(dummy, to1D(i, j))) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    
        class UnionFindSet {
            Map<Integer, Integer> parent;

            public UnionFindSet() {
                this.parent = new HashMap<>();
                int t;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        t = to1D(i, j);
                        parent.put(t, t);
                    }
                }
                parent.put(-1, -1); //虚拟节点
            }

            public void union(int n1, int n2) {
                int r1 = find(n1), r2 = find(n2);
                if (r1 == r2) return;
                else {
                    if (r1 <= r2) {
                        parent.put(r2, r1);
                    } else {
                        parent.put(r1, r2);
                    }
                }
            }

            public int find(int n) {
                int p;
                if ((p = parent.get(n)) == n) {
                    return n;
                }
                int r = find(p);
                parent.put(n, r);
                return r;
            }

            public boolean isConnect(int n1, int n2) {
                return find(n1) == find(n2);
            }
        } 

        public int to1D(int i, int j) {
            return i * m + j;
        }
        public int[] to2D(int idx) {
            return new int[]{idx / m, idx % n};
        }
    }


    
    class Solution2 { //BFS方法：将下个位置的下标记录下来再去改
        int m,n;
        char[][] board;
        int[][] flag;
        //改动原数组，将边界有关的O全部变成另外的字符最后再变回来
        public void solve(char[][] board) {
            if (board == null) return;
            this.m = board.length;
            this.n = board[0].length;
            this.board = board;
            chargeEdges('O', 'B');
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                }
            }      
            chargeEdges('B', 'O');
        }

        public void chargeEdges(char src, char other) {
            for (int i = 0; i < m; i++) {
                if (board[i][0] == src) {
                    bfs(i, 0, src, other);
                }
                if (board[i][n - 1] == src) {
                    bfs(i, n - 1, src, other);
                }
            }

            for (int i = 0; i < n; i++) {
                if (board[0][i] == src) {
                    bfs(0, i, src, other);
                }
                if (board[m - 1][i] == src) {
                    bfs(m - 1, i, src, other);
                }
            }
        }

        public void bfs(int i, int j, char src, char other) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{i, j});
            while (!queue.isEmpty()) {
                int n = queue.size();
                for (int k = 0; k < n; k++) {
                    int[] cur = queue.poll();
                    board[cur[0]][cur[1]] = other;
                    if (cur[0] - 1 >= 0 && board[cur[0] - 1][cur[1]] == src) {
                        queue.offer(new int[]{cur[0] - 1, cur[1]});
                    }
                    if (cur[1] - 1 >= 0 && board[cur[0]][cur[1] - 1] == src) {
                        queue.offer(new int[]{cur[0], cur[1] - 1});
                    }
                    if (cur[0] + 1 < m && board[cur[0] + 1][cur[1]] == src)  {
                        queue.offer(new int[]{cur[0] + 1, cur[1]});
                    }
                    if (cur[1] + 1 < n && board[cur[0]][cur[1] + 1] == src) {
                        queue.offer(new int[]{cur[0], cur[1] + 1});
                    }
                }
            }
        }

    }

    class Solution1 {
        int m,n;
        char[][] board;
        int[][] flag;
        //改动原数组，将边界有关的O全部变成另外的字符最后再变回来
        public void solve(char[][] board) {
            if (board == null) return;
            this.m = board.length;
            this.n = board[0].length;
            this.board = board;
            this.flag = new int[m][n];
            chargeEdges('O', 'B');
            System.out.println(Arrays.deepToString(board));

            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                }
            }          
            chargeEdges('B', 'O');
        }

        public void chargeEdges(char src, char other) {
            for (int i = 0; i < m; i++) {
                if (board[i][0] == src) {
                    dfs(i, 0, src, other);
                }
                if (board[i][n - 1] == src) {
                    dfs(i, n - 1, src, other);
                }
            }

            for (int i = 0; i < n; i++) {
                if (board[0][i] == src) {
                    dfs(0, i, src, other);
                }
                if (board[m - 1][i] == src) {
                    dfs(m - 1, i, src, other);
                }
            }
        }

        public void dfs(int i, int j, char src, char other) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                return;
            }
            if (board[i][j] != src) return;
            board[i][j] = other;
            dfs(i + 1, j, src, other);
            dfs(i - 1, j, src, other);
            dfs(i, j + 1, src, other);
            dfs(i, j - 1, src, other);
        }
    }
    class SolutionX {
        int m,n;
        char[][] board;
        int[][] flag;
        public void solve(char[][] board) {
            if (board == null) return;
            this.m = board.length;
            this.n = board[0].length;
            this.board = board;
            this.flag = new int[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O' && flag[i][j] == 0) {
                        dfs(i, j);
                    }
                }
            }
        }

        public boolean dfs(int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                // flag[i][j] = 2;
                return false; //某一个时刻达到边界外，证明不连通
            }
            if (flag[i][j] != 0) return flag[i][j] == 1;
            if (board[i][j] == 'X') {
                flag[i][j] = 1;
                return true;
            }
            if (dfs(i - 1, j) && dfs(i + 1, j) && dfs(i, j - 1) && dfs(i, j + 1)) {
                board[i][j] = 'X';
                flag[i][j] = 1;
                return true;
            } else {
                flag[i][j] = 2;
                return false;
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        char[][] board = {new char[]{'X','X','X','X'},new char[]{'X','O','O','X'},new char[]{'X','X','O','X'},new char[]{'X','O','X','X'}};
        s.solve(board);
        System.out.println(Arrays.deepToString(board));
    }
}
